home *** CD-ROM | disk | FTP | other *** search
/ Aminet 28 / Aminet 28 (1998)(GTI - Schatztruhe)[!][Dec 1998].iso / Aminet / dev / c / qtools0.2-src.lha / src / libqbuild / csg4.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-07-15  |  10.4 KB  |  448 lines
  1. #define    LIBQBUILD_CORE
  2. #include "../include/libqbuild.h"
  3.  
  4. /*
  5.  * 
  6.  * NOTES
  7.  * -----
  8.  * Brushes that touch still need to be split at the cut point to make a tjunction
  9.  * 
  10.  */
  11.  
  12. struct visfacet **validfaces;
  13.  
  14. struct visfacet *inside, *outside;                /* 8 */
  15. int brushfaces;                            /* 4 */
  16. int csgfaces;                            /* 4 */
  17. int csgmergefaces;                        /* 4 */
  18.  
  19. void DrawList(register struct visfacet *list)
  20. {
  21.   for (; list; list = list->next)
  22.     Draw_DrawFace(list);
  23. }
  24.  
  25. /*
  26.  * ==================
  27.  * NewFaceFromFace
  28.  * 
  29.  * Duplicates the non point information of a face, used by SplitFace and
  30.  * MergeFace.
  31.  * ==================
  32.  */
  33. struct visfacet *NewFaceFromFace(register struct visfacet *in, register int points)
  34. {
  35.   struct visfacet *newf;
  36.  
  37.   newf = AllocFace(points);
  38.  
  39.   newf->planenum = in->planenum;
  40.   newf->texturenum = in->texturenum;
  41.   newf->planeside = in->planeside;
  42.   newf->original = in->original;
  43.   newf->contents[0] = in->contents[0];
  44.   newf->contents[1] = in->contents[1];
  45.  
  46.   return newf;
  47. }
  48.  
  49. /*
  50.  * ==================
  51.  * SplitFace
  52.  * 
  53.  * ==================
  54.  */
  55. void SplitFace(struct visfacet *in, struct plane *split, struct visfacet **front, struct visfacet **back)
  56. {
  57.   vec_t *dists = (vec_t *) tmalloc(MAXEDGES * sizeof(vec_t));
  58.   int *sides = (int *)tmalloc(MAXEDGES * sizeof(int));
  59.   int counts[3];
  60.   vec_t dot;
  61.   int i, j;
  62.   struct visfacet *newf, *new2;
  63.   vec_t *p1, *p2;
  64.   vec3_t mid;
  65.  
  66.   if (in->numpoints < 0)
  67.     Error("SplitFace: freed face");
  68.   counts[0] = counts[1] = counts[2] = 0;
  69.  
  70.   /* determine sides for each point */
  71.   for (i = 0; i < in->numpoints; i++) {
  72.     dot = DotProduct(in->pts[i], split->normal);
  73.     dot -= split->dist;
  74.     dists[i] = dot;
  75.     if (dot > ON_EPSILON)
  76.       sides[i] = SIDE_FRONT;
  77.     else if (dot < -ON_EPSILON)
  78.       sides[i] = SIDE_BACK;
  79.     else
  80.       sides[i] = SIDE_ON;
  81.     counts[sides[i]]++;
  82.   }
  83.   sides[i] = sides[0];
  84.   dists[i] = dists[0];
  85.  
  86.   if (!counts[0]) {
  87.     *front = NULL;
  88.     *back = in;
  89.     tfree(dists);
  90.     tfree(sides);
  91.     return;
  92.   }
  93.   if (!counts[1]) {
  94.     *front = in;
  95.     *back = NULL;
  96.     tfree(dists);
  97.     tfree(sides);
  98.     return;
  99.   }
  100.  
  101.   *back = newf = NewFaceFromFace(in, MAXEDGES);
  102.   *front = new2 = NewFaceFromFace(in, MAXEDGES);
  103.  
  104.   /* distribute the points and generate splits */
  105.   for (i = 0; i < in->numpoints; i++) {
  106.     if (newf->numpoints > MAXEDGES || new2->numpoints > MAXEDGES)
  107.       Error("SplitFace: numpoints > MAXEDGES");
  108.  
  109.     p1 = in->pts[i];
  110.  
  111.     if (sides[i] == SIDE_ON) {
  112.       VectorCopy(p1, newf->pts[newf->numpoints]);
  113.       newf->numpoints++;
  114.       VectorCopy(p1, new2->pts[new2->numpoints]);
  115.       new2->numpoints++;
  116.       continue;
  117.     }
  118.  
  119.     if (sides[i] == SIDE_FRONT) {
  120.       VectorCopy(p1, new2->pts[new2->numpoints]);
  121.       new2->numpoints++;
  122.     }
  123.     else {
  124.       VectorCopy(p1, newf->pts[newf->numpoints]);
  125.       newf->numpoints++;
  126.     }
  127.  
  128.     if (sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i])
  129.       continue;
  130.  
  131.     /* generate a split point */
  132.     p2 = in->pts[(i + 1) % in->numpoints];
  133.  
  134.     dot = dists[i] / (dists[i] - dists[i + 1]);
  135.     for (j = 0; j < 3; j++) {                    /* avoid round off error when possible */
  136.       if (split->normal[j] == 1)
  137.     mid[j] = split->dist;
  138.       else if (split->normal[j] == -1)
  139.     mid[j] = -split->dist;
  140.       else
  141.     mid[j] = p1[j] + dot * (p2[j] - p1[j]);
  142.     }
  143.  
  144.     VectorCopy(mid, newf->pts[newf->numpoints]);
  145.     newf->numpoints++;
  146.     VectorCopy(mid, new2->pts[new2->numpoints]);
  147.     new2->numpoints++;
  148.   }
  149.  
  150.   if (newf->numpoints > MAXEDGES || new2->numpoints > MAXEDGES)
  151.     Error("SplitFace: numpoints > MAXEDGES");
  152.  
  153.   RecalcFace(newf);
  154.   RecalcFace(new2);
  155. #ifdef EXHAUSIVE_CHECK
  156.   if ((newf->numpoints > in->numpoints) || (new2->numpoints > in->numpoints))
  157.     Error("SplitFace: heavy split (%d to %d + %d)\n", in->numpoints, newf->numpoints, new2->numpoints);
  158. #endif
  159.  
  160. #if 0
  161.   CheckFace(newf);
  162.   CheckFace(new2);
  163. #endif
  164.  
  165.   /* free the original face now that is is represented by the fragments */
  166.   FreeFace(in);
  167.   tfree(dists);
  168.   tfree(sides);
  169. }
  170.  
  171. /*
  172.  * =================
  173.  * ClipInside
  174.  * 
  175.  * Clips all of the faces in the inside list, possibly moving them to the
  176.  * outside list or spliting it into a piece in each list.
  177.  * 
  178.  * Faces exactly on the plane will stay inside unless overdrawn by later brush
  179.  * 
  180.  * frontside is the side of the plane that holds the outside list
  181.  * =================
  182.  */
  183. void ClipInside(__memBase, register int splitplane, register int frontside, register bool precedence)
  184. {
  185.   struct visfacet *f, *next;
  186.   struct visfacet *frags[2];
  187.   struct visfacet *insidelist;
  188.   struct plane *split;
  189.  
  190. #ifdef EXHAUSIVE_CHECK
  191.   if (splitplane >= bspMem->numbrushplanes || splitplane < 0)
  192.     Error("looking for nonexisting plane %d\n", splitplane);
  193. #endif
  194.   split = &bspMem->brushplanes[splitplane];
  195.  
  196.   insidelist = NULL;
  197.   for (f = inside; f; f = next) {
  198.     next = f->next;
  199.  
  200.     if (f->planenum == splitplane) {                /* exactly on, handle special */
  201.       if (frontside != f->planeside || precedence) {        /* allways clip off opposite faceing */
  202.     frags[frontside] = NULL;
  203.     frags[!frontside] = f;
  204.       }
  205.       else {                            /* leave it on the outside */
  206.     frags[frontside] = f;
  207.     frags[!frontside] = NULL;
  208.       }
  209.     }
  210.     else {                            /* proper split */
  211.       SplitFace(f, split, &frags[0], &frags[1]);
  212.     }
  213.  
  214.     if (frags[frontside]) {
  215.       frags[frontside]->next = outside;
  216.       outside = frags[frontside];
  217.     }
  218.     if (frags[!frontside]) {
  219.       frags[!frontside]->next = insidelist;
  220.       insidelist = frags[!frontside];
  221.     }
  222.   }
  223.  
  224.   inside = insidelist;
  225. }
  226.  
  227. /*
  228.  * ==================
  229.  * SaveOutside
  230.  * 
  231.  * Saves all of the faces in the outside list to the bsp plane list
  232.  * ==================
  233.  */
  234. void SaveOutside(__memBase, register bool mirror)
  235. {
  236.   struct visfacet *f, *next, *newf;
  237.   int i;
  238.   int planenum;
  239.  
  240.   for (f = outside; f; f = next) {
  241.     next = f->next;
  242.     csgfaces++;
  243.     Draw_DrawFace(f);
  244.     planenum = f->planenum;
  245.  
  246.     if (mirror) {
  247.       newf = NewFaceFromFace(f, f->numpoints);
  248.  
  249.       newf->numpoints = f->numpoints;
  250.       newf->planeside = f->planeside ^ 1;            /* reverse side */
  251.  
  252.       newf->contents[0] = f->contents[1];
  253.       newf->contents[1] = f->contents[0];
  254.  
  255.       for (i = 0; i < f->numpoints; i++)            /* add points backwards */
  256.     VectorCopy(f->pts[f->numpoints - 1 - i], newf->pts[i]);
  257.     }
  258.     else
  259.       newf = NULL;
  260.  
  261.     validfaces[planenum] = MergeFaceToList(bspMem, f, validfaces[planenum]);
  262.     if (newf)
  263.       validfaces[planenum] = MergeFaceToList(bspMem, newf, validfaces[planenum]);
  264.  
  265.     validfaces[planenum] = FreeMergeListScraps(validfaces[planenum]);
  266.   }
  267. }
  268.  
  269. /*
  270.  * ==================
  271.  * FreeInside
  272.  * 
  273.  * Free all the faces that got clipped out
  274.  * ==================
  275.  */
  276. void FreeInside(register int contents)
  277. {
  278.   struct visfacet *f, *next;
  279.  
  280.   for (f = inside; f; f = next) {
  281.     next = f->next;
  282.  
  283.     if (contents != CONTENTS_SOLID) {
  284.       f->contents[0] = contents;
  285.       f->next = outside;
  286.       outside = f;
  287.     }
  288.     else
  289.       FreeFace(f);
  290.   }
  291. }
  292.  
  293. /*========================================================================== */
  294.  
  295. /*
  296.  * ==================
  297.  * BuildSurfaces
  298.  * 
  299.  * Returns a chain of all the external surfaces with one or more visible
  300.  * faces.
  301.  * ==================
  302.  */
  303. struct surface *BuildSurfaces(__memBase)
  304. {
  305.   struct visfacet **f;
  306.   struct visfacet *count;
  307.   int i;
  308.   struct surface *s;
  309.   struct surface *surfhead;
  310.  
  311.   surfhead = NULL;
  312.  
  313.   f = validfaces;
  314.   for (i = 0; i < bspMem->numbrushplanes; i++, f++) {
  315.     if (*f) {                            /* !nothing left on this plane */
  316.       /* create a new surface to hold the faces on this plane */
  317.       s = AllocSurface();
  318.       s->planenum = i;
  319.       s->next = surfhead;
  320.       surfhead = s;
  321.       s->faces = *f;
  322.       for (count = s->faces; count; count = count->next)
  323.     csgmergefaces++;
  324.       CalcSurfaceInfo(s);                    /* bounding box and flags */
  325.     }
  326. /** mprogress(bspMem->numbrushplanes, i + 1); **/
  327.   }
  328.  
  329.   return surfhead;
  330. }
  331.  
  332. /*========================================================================== */
  333.  
  334. /*
  335.  * ==================
  336.  * CopyFacesToOutside
  337.  * ==================
  338.  */
  339. void CopyFacesToOutside(register struct brush *b)
  340. {
  341.   struct visfacet *f, *newf;
  342.  
  343.   outside = NULL;
  344.  
  345.   for (f = b->faces; f; f = f->next) {
  346.     brushfaces++;
  347. #if 0
  348.     {
  349.       int i;
  350.  
  351.       for (i = 0; i < f->numpoints; i++)
  352.     mprintf("(%f,%f,%f) ", f->pts[i][0], f->pts[i][1], f->pts[i][2]);
  353.       mprintf("\n");
  354.     }
  355. #endif
  356.     newf = AllocFace(f->numpoints);
  357.     CopyFace(newf, f);
  358.     newf->next = outside;
  359.     newf->contents[0] = CONTENTS_EMPTY;
  360.     newf->contents[1] = b->contents;
  361.     outside = newf;
  362.   }
  363. }
  364.  
  365. /*
  366.  * ==================
  367.  * CSGFaces
  368.  * 
  369.  * Returns a list of surfaces containing aall of the faces
  370.  * ==================
  371.  */
  372. struct surface *CSGFaces(__memBase, struct brushset *bs)
  373. {
  374.   struct brush *b1, *b2;
  375.   int i, j;
  376.   bool overwrite;
  377.   struct visfacet *f;
  378.   struct surface *surfhead;
  379.  
  380.   mprintf("----- CSGFaces ----------\n");
  381.  
  382.   if (!(validfaces = (struct visfacet **)tmalloc(sizeof(struct visfacet *) * bspMem->numbrushplanes)))
  383.       Error(failed_memoryunsize, "validfaces");
  384.  
  385.   csgfaces = brushfaces = csgmergefaces = 0;
  386.  
  387.   Draw_ClearWindow();
  388.  
  389.   /* do the solid faces */
  390.   for (b1 = bs->brushes, j = 0; b1; b1 = b1->next) {
  391.     mprogress(bs->numbrushes, ++j);
  392.  
  393.     /* set outside to a copy of the brush's faces */
  394.     CopyFacesToOutside(b1);
  395.  
  396.     overwrite = FALSE;
  397.  
  398.     for (b2 = bs->brushes; b2; b2 = b2->next) {
  399.       /* see if b2 needs to clip a chunk out of b1 */
  400.       if (b1 == b2) {
  401.     overwrite = TRUE;                    /* later brushes now overwrite */
  402.     continue;
  403.       }
  404.  
  405.       /* check bounding box first */
  406.       for (i = 0; i < 3; i++)
  407.     if (b1->mins[i] > b2->maxs[i] || b1->maxs[i] < b2->mins[i])
  408.       break;
  409.       if (i < 3)
  410.     continue;
  411.  
  412.       /* divide faces by the planes of the new brush */
  413.       inside = outside;
  414.       outside = NULL;
  415.  
  416.       for (f = b2->faces; f; f = f->next)
  417.     ClipInside(bspMem, f->planenum, f->planeside, overwrite);
  418.  
  419.       /* these faces are continued in another brush, so get rid of them */
  420.       if (b1->contents == CONTENTS_SOLID && b2->contents <= CONTENTS_WATER)
  421.     FreeInside(b2->contents);
  422.       else
  423.     FreeInside(CONTENTS_SOLID);
  424.     }
  425.  
  426.     /* all of the faces left in outside are real surface faces */
  427.     if (b1->contents != CONTENTS_SOLID)
  428.       SaveOutside(bspMem, TRUE);                /* mirror faces for inside view */
  429.  
  430.     else
  431.       SaveOutside(bspMem, FALSE);
  432.   }
  433.  
  434. #if 0
  435.   if (!csgfaces)
  436.     Error("No faces");
  437. #endif
  438.  
  439.   surfhead = BuildSurfaces(bspMem);
  440.  
  441.   mprintf("%5i brushfaces\n", brushfaces);
  442.   mprintf("%5i csgfaces\n", csgfaces);
  443.   mprintf("%5i mergedfaces\n", csgmergefaces);
  444.  
  445.   tfree(validfaces);
  446.   return surfhead;
  447. }
  448.